package com.github.hgkmail.hello.leetcode101.dualpointer;

import com.github.hgkmail.hello.leetcode101.base.ListNode;

public class LC142LinkedListCycle2 {
    public ListNode detectCycle(ListNode head) {
        ListNode fast=head;
        ListNode slow=head;
        do {
            if (fast==null || fast.next==null) {
                return null; //走到尽头，不存在环
            }
            fast=fast.next.next;
            slow=slow.next;
        } while (fast!=slow);
        //相遇存在环，把fast或者slow移到到开头
        slow=head;
        while (fast!=slow) {
            fast=fast.next;
            slow=slow.next;
        }
        //再次相遇，是环的入口节点
        return slow;
    }

    public static void main(String[] args) {

    }
}
